/// 1. 引入头文件
#include <vector>
#include <iostream>
#include <algorithm>

/// 2. 打开名字空间
using namespace std;

// 算法写这里
// 4. 规划好输入：接受任意一个数组 vector<int>
// 5. 规划好输出：返回一个按照从小到大排列的数组 vector<int>
// bubbleSort 驼峰式命名
// bubble_sort 蛇形命名
vector<int> bubbleSort(vector<int> arr) {
  int round = 0;

  /*
   * arr.size() == 9 | r: 8
   * 0 ---- arr.size() - 2
   * 0 ---- 7
   * */

  while (round != arr.size() - 1) {
    /* 不断的比较和交换数组元素*/
    for (int i = arr.size() - 1; i > round; --i) {
      if (arr[i - 1] > arr[i]) {
        swap(arr[i - 1], arr[i]);
      }
    }

    ++round;
  }

  return arr;
}

/// 3. 创建入口函数 main
int main(int argc, char const *argv[])
{
  /* code */
  vector<int> v {1, 4, 3, 6, 8, 7, 2, 5, 9};
  auto sorted = bubbleSort(v);

  for (auto n : sorted) {
    cout<<n<<" ";
  }

  cout<<endl;
  return 0;
}

